package cn.hughie.linked;

import java.util.LinkedList;
import java.util.List;
import java.util.Random;

/**
 * @Author yuh
 * @Date Created in 上午11:36 2018/5/27
 * @Description 跳表
 */
public class SkipList<T> {

    private class SkipListNode {
        SkipListNode next;
        SkipListNode down;
        double score;
        T val;

        public SkipListNode(double score, T val) {
            this.score = score;
            this.val = val;
        }
    }

    private int level;
    private SkipListNode top;
    private Random random = new Random();
    private static final int MAX_LEVEL = 2 << 6;


    public SkipList() {
        this(4);
    }

    public SkipList(int level) {
        SkipListNode temp = null, downTemp = null;
        this.level = level;
        while (level-- != 0) {
            temp = new SkipListNode(Double.MIN_VALUE, null);
            temp.down = downTemp;
            downTemp = temp;
        }
        top = temp;
    }

    private int getLevel() {
        int level = 1;
        while (Math.abs(random.nextInt()) % 2 == 0) {
            level++;
        }
        return level > MAX_LEVEL ? MAX_LEVEL : level;
    }


    public T get(double score) {
        SkipListNode findNodeTemp = top;
        while (findNodeTemp != null) {
            //先匹配自己的值
            if (findNodeTemp.score == score) {
                return findNodeTemp.val;
            }

            //看下一个是否存在
            if (findNodeTemp.next == null) {
                //往自己下面查找
                findNodeTemp = findNodeTemp.down;
                continue;
            } else {
                if (score < findNodeTemp.next.score) {
                    findNodeTemp = findNodeTemp.down;
                } else {
                    findNodeTemp = findNodeTemp.down;
                }
            }
        }
        return null;
    }

    public void put(double score, T val) {
        SkipListNode findNodeTemp = top, cur = null;
        LinkedList<SkipListNode> successors = new LinkedList<>();
        while (findNodeTemp != null) {
            //先匹配自己的值
            if (findNodeTemp.score == score) {
                cur = findNodeTemp;
                break;
            }

            //看下一个是否存在
            if (findNodeTemp.next == null) {
                //往自己下面查找
                successors.addLast(findNodeTemp);
                findNodeTemp = findNodeTemp.down;
                continue;
            } else {
                if (score < findNodeTemp.next.score) {
                    successors.addLast(findNodeTemp);
                    findNodeTemp = findNodeTemp.down;
                } else {
                    findNodeTemp = findNodeTemp.next;
                }
            }
        }
        //说明已经找到 要按照层级进行替换
        if (cur != null) {
            while (cur != null) {
                cur.val = val;
                cur = cur.down;
            }
        } else {
            //没找到
            //判断新节点插多高
            int newLevel = getLevel();
            SkipListNode newTop = null;
            SkipListNode temp = top;
            for (int i = level + 1; i <= newLevel; i++) {
                newTop = new SkipListNode(Double.MIN_VALUE, null);
                //越靠上层top节点 越在上面
                successors.addFirst(newTop);
                newTop.down = temp;
                temp = newTop;
            }
            level = newLevel > level ? newLevel : level;
            top = temp;

            //插入新节点 自底向上插入
            SkipListNode newNode = null;
            SkipListNode prev = null, downTemp = null;
            for (int i = newLevel - 1; i >= 0; i--) {
                //从集合中取出 并把新元素放到后面
                newNode = new SkipListNode(score, val);
                prev = successors.removeLast();
                newNode.next = prev.next;
                prev.next = newNode;
                newNode.down = downTemp;
                downTemp = newNode;
            }
        }
    }

    public void delete(double score) {
        SkipListNode findNodeTemp = top;
        while (findNodeTemp != null) {
            //判断下一个存在吗
            if (findNodeTemp.next != null) {
                if (findNodeTemp.next.score == score) {
                    //删除
                    findNodeTemp.next = findNodeTemp.next.next;
                    continue;
                }

                if (findNodeTemp.next.score > score) {
                    findNodeTemp = findNodeTemp.down;
                } else {
                    findNodeTemp = findNodeTemp.next;
                }
            }
        }
    }

    @Override
    public String toString() {
        int l = level;
        SkipListNode strNode = top;
        StringBuilder sb = new StringBuilder();
        sb.append(l);
        while (strNode != null) {
            sb.append("[").append(strNode.val).append(",").append(strNode.score).append("]");
            if (strNode.next != null) {
                strNode = strNode.next;
                continue;
            }
            strNode = strNode.down;
            sb.append("\n");
            sb.append(--l);
        }
        return sb.toString();
    }

    public static void main(String[] args) {
        SkipList<String> list = new SkipList<>();
        list.put(1.0, "1.0");
        //System.out.println(list);
        /*list.put(2.0, "2.0");
       // System.out.println(list);
        list.put(3.0, "3.0");
       // System.out.println(list);
        list.put(4.0, "4.0");
      //  System.out.println(list);
        list.put(4.0, "5.0");*/
        System.out.println(list);
        //  list.delete(3.0);
        // list.delete(3.5);
        //  System.out.println(list);
        //  System.out.println("查找4.0" + list.get(4.0));
    }
}
